{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# My Own ArrayList / Dynamic Array\n",
    "\n",
    "- ADT List Operations\n",
    "    - Create an empty list\n",
    "    - Determine whether the list is empty\n",
    "    - Determine the number of items in a list\n",
    "    - Add an item at given position in a list\n",
    "    - Remove the item at a given position in a list\n",
    "    - Remove all the items from a list\n",
    "    - Get the item at a given position in a list\n",
    "    - Other operations?  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "import ctypes\n",
    "\n",
    "class DynamicArray:\n",
    "    \n",
    "    def __init__ (self):\n",
    "        'Create an empty array.'\n",
    "        self.size = 0\n",
    "        self.capacity = 2\n",
    "        self.A = self._make_array(self.capacity)\n",
    "        \n",
    "    # len(list)\n",
    "    def __len__ (self):\n",
    "        \n",
    "        return self.size\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self.size==0\n",
    "    \n",
    "    # O(1)\n",
    "    def __getitem__ (self, k):\n",
    "        if not 0<=k<self.size:\n",
    "            raise ValueError(\"invalid index\")\n",
    "        return self.A[k]\n",
    "       \n",
    "    # O(1) \n",
    "    def append(self, obj):\n",
    "        if self.size==self.capacity:\n",
    "            self._resize(2*self.capacity)\n",
    "        self.A[self.size] = obj\n",
    "        self.size+=1\n",
    "    def _make_array(self, c):\n",
    "        A =(c*ctypes.py_object)()\n",
    "        return A\n",
    "\n",
    "    \n",
    "    def _resize(self, c):\n",
    "        temp = self._make_array(c)\n",
    "        for i,item in enumerate(self.A):\n",
    "            temp[i] = item\n",
    "        self.A = temp\n",
    "        self.capacity = c\n",
    "\n",
    "    # O(n)\n",
    "    def insert(self, k, value):\n",
    "        if self.size==self.capacity:\n",
    "            self._resize(2*self.capacity)\n",
    "        for i in range(self.size-1,k-1,-1):\n",
    "            self.A[i+1] = self.A[i]\n",
    "        self.A[k] = value\n",
    "        self.size+=1\n",
    "     \n",
    "    # O(n)    \n",
    "    def remove(self, value):\n",
    "        for i,item in enumerate(self.A):\n",
    "            if item == value:\n",
    "                for j in range(i,self.size-1):\n",
    "                    self.A[j] = self.A[j+1]\n",
    "                self.A[self.size-1] = None\n",
    "                self.size-=1\n",
    "                return\n",
    "        raise ValueError('value not found')\n",
    "\n",
    "    \n",
    "    def _print(self):\n",
    "        for i in range(self.size):\n",
    "            print(self.A[i],end=' ')\n",
    "            print()\n",
    "    def _pop(self,index=None):\n",
    "        if index==None:\n",
    "            index = self.size-1\n",
    "        if not 0<=index<self.size:\n",
    "            raise ValueError('invalid index')\n",
    "        pop_value = self.A[index] \n",
    "        for i in range(index,self.size-1):\n",
    "            self.A[i] = self.A[i+1]\n",
    "        return pop_value          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "size was:  0\n",
      "0 \n",
      "5 \n",
      "10 \n",
      "15 \n",
      "20 \n",
      "30 \n",
      "0 \n",
      "5 \n",
      "10 \n",
      "15 \n",
      "30 \n",
      "size is:  5\n"
     ]
    }
   ],
   "source": [
    "mylist = DynamicArray()\n",
    "print ('size was: ', str(len(mylist)))\n",
    "mylist.append(10)\n",
    "mylist.append(20)\n",
    "mylist.append(30)\n",
    "mylist.insert(0, 0)\n",
    "mylist.insert(1, 5)\n",
    "mylist.insert(3, 15)\n",
    "mylist._print()\n",
    "mylist.remove(20)\n",
    "mylist._print()\n",
    "\n",
    "print ('size is: ', str(len(mylist)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "30"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist._pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
